package com.kehao.leetcode.algorithm;


import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;

//https://leetcode-cn.com/problems/longest-palindromic-substring/
public class Solution5 {

    public String longestPalindrome(String s) {
        int length = s.length();
        char[] charArray = s.toCharArray();
        boolean[][] isPalindromeArray = new boolean[length][length];
        String longest = null;
        int maxLength = 0;

        for (int i = 0; i < length; i++) {//i表示子字符串的长度-1
            for (int j = 0; j < length-i; j++) { //子字符串是 j到j+i
                if(i ==0){
                    isPalindromeArray[j][j+i] = true;
                }else if(i==1){
                    isPalindromeArray[j][j+i] = charArray[j] == charArray[j+i];
                }else {
                    isPalindromeArray[j][j+i] = charArray[j] == charArray[j+i] && isPalindromeArray[j+1][j+i-1];
                }
                if(isPalindromeArray[j][j+i]&&maxLength<i+1){
                    maxLength = i+1;
                    longest = s.substring(j,j+i+1);
                }
            }
        }

        return  longest;
    }


    @Test
    public void myTest() {
        String substring = "123".substring(0, 3);
        System.out.println(substring);
    }

    @Test
    public void myTest1() {
        String s = "babad";
        System.out.println(longestPalindrome(s));
    }
}
